package Leetcode.sliding_window;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/10/18 16:03
 * @Description:
 * 给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。
 *
 * 在 moveFrom.length 次操作内，你将改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。
 *
 * 完成这些操作后，请你按升序返回所有 有 石块的位置。
 *
 * 注意：
 *
 * 如果一个位置至少有一个石块，我们称这个位置 有 石块。
 * 一个位置可能会有多个石块。
 *
 * 示例 1：
 *
 * 输入：nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
 * 输出：[5,6,8,9]
 * 解释：一开始，石块在位置 1,6,7,8 。
 * 第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。
 * 第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。
 * 第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。
 * 最后，至少有一个石块的位置为 [5,6,8,9] 。
 */

public class 重新放置石块 {
    /**
     *
     * @param nums  石块的初始位置
     * @param moveFrom  将from的位置的石头
     * @param moveTo    移动到to的位置
     * @return  该位置有石头的索引
     */
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Set<Integer> set = new HashSet<>(nums.length); // 预分配空间，效率更高
        for (int x : nums) {
            set.add(x);
        }

        for (int i = 0; i < moveFrom.length; i++) {
            set.remove(moveFrom[i]);
            set.add(moveTo[i]);
        }

        List<Integer> ans = new ArrayList<>(set);
        Collections.sort(ans);
        return ans;
    }

    /**
     * 给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
     *
     * 如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。
     * 例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （
     * 相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。
     *
     * 请你返回 s 中最长 半重复子字符串的长度。
     */
    public int longestSemiRepetitiveSubstring(String S) {
        char[] s = S.toCharArray();
        int max_len = 1;
        //上一个重复字符的位置
        int pt = -1;
        int left = 0;
        for (int right = 1; right < s.length; right++) {
            if (s[right] == s[right - 1]) {
                // 更新左边界为上一个重复字符的下一个位置
                left = pt + 1;
                // 更新上一个重复字符的位置为当前字符的前一个位置
                pt = right - 1;
            }
            max_len = Math.max(max_len, right - left + 1);
        }
        return max_len;
    }

    /**
     * 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
     *
     * 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
     *
     * 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
     * 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
     * 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
     * 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
     *
     * 示例 1：
     *
     * 输入：fruits = [1,2,1]
     * 输出：3
     * 解释：可以采摘全部 3 棵树。
     * 示例 2：
     *
     * 输入：fruits = [0,1,2,2]
     * 输出：3
     * 解释：可以采摘 [1,2,2] 这三棵树。
     * 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
     */
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) {
                    cnt.remove(fruits[left]);
                }
                ++left;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
     *
     * 给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。
     * skills 中所有整数 互不相同 。
     *
     * 所有玩家从编号 0 到 n - 1 排成一列。
     *
     * 比赛进行方式如下：
     *
     * 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
     * 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
     * 这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
     *
     * 请你返回这个比赛的赢家编号。
     *
     *
     * 输入：skills = [4,2,6,3,9], k = 2
     *
     * 输出：2
     *
     * 解释：
     *
     * 一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：
     *
     * 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。
     * 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。
     * 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。
     * 玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。
     *
     * 模拟
     */
    public int findWinningPlayer_simulate(int[] skills, int K) {
        // 求队列中的最大值
        int mx = 0;

        // 把能力值和下标加入双端队列
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < skills.length; i++) {
            q.add(new int[]{skills[i], i});
            mx = Math.max(skills[i], mx);
        }

        int win = 0;
        while (true) {
            // 模拟比赛过程
            int[] x = q.pollFirst();
            int[] y = q.pollFirst();
            if (x[0] > y[0]) {
                win++;
                q.offerFirst(x);
                q.offerLast(y);
            } else {
                //相当于a输了，b赢了一场，重置win为1
                win = 1;
                q.offerFirst(y);
                q.offerLast(x);
            }
            // 如果队头满足赢家条件，或最大值来到了队头，则队头就是赢家
            if (win >= K || q.peekFirst()[0] == mx) {
                return q.peekFirst()[1];
            }
        }
    }

    /**
     *      首先查看题解了解思路的大概，但是可能存在疑惑为什么这么一次遍历就会出结果呢，而不会丢失结果呢？
     *      首先，单看for循环，找到一个最大值是一定满足题意的，这个我们需要从题解中明白
     *      其次，为什么一次遍历就可以，在最简单的情况，也就是第一个值就比较大，但是不是最大，
     *  然后后面的k个数都满足比第一个值要小，那么每次都会win++，就得出结果了，这个逻辑好理解。
     *      现在，如果说只有少于k个数符合要求，此时在遇到一个新的比tempMax大的数时就会更新tempMax，
     *  此时就会有两种情况：
     *          1.此时后面存在k个数比tempMax小，返回tempMax即可
     *          2.不存在k个数，会再次更新tempMax，以此循环，一直遍历到数组结尾，都不存在k个数使其跳出循环
     *  那么，这个最大的数就是我们要找的结果，也就是第一点的题意。
     *      over。
     */
    public int findWinningPlayer(int[] skills, int k) {
        int maxI = 0;
        int win = 0;
        for (int i = 1; i < skills.length && win < k; i++) {
            if (skills[i] > skills[maxI]) { // 打擂台，发现新的最大值
                maxI = i;
                win = 0;
            }
            win++; // 获胜回合 +1
        }
        // 如果 k 很大，那么 maxI 就是 skills 最大值的下标，毕竟最大值会一直赢下去
        return maxI;
    }


}
